﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>

//int main()
//{
//	printf("hehe\n");
//	main();
//
//	return 0;
//}


//举例1：求n的阶乘
// n! = (n-1)! * n


// 一、递归
//int Fact(int n)
//{
//	
//	if (n == 0)
//	{
//		return 1;
//
//	}
//	else
//		return Fact(n - 1) * n;
//
//
//}
//
//
//
//int main()
//{
//	int n = 0;
//	printf("计算阶乘\n");
//	scanf("%d",&n);
//	int sum = Fact(n);
//	printf("%d",sum);
//	return 0;
//}

//二、循环

//int fact(int n )
//{
//	int sum = 1;
//	if (n == 0)
//	{
//		return sum;
//	}
//	else
//	{
//		int i = 0;
//		for (i = 1; i <= n; i++)
//		{
//			sum *= i;
//		}
//		return sum;
//	}
//
//}
//
//
//int main()
//{
//	int n = 0;
//	printf("计算阶乘\n");
//	scanf("%d",&n);
//	int sum = fact(n);
//	printf("%d",sum);
//
//	return 0;
//}


//举例2：顺序打印⼀个整数的每⼀位

//void Print(int n )
//{
//	if (n > 9)
//	{
//		Print(n / 10);
//	}
//	printf("%d ",n%10);
//}
//
//
//
//
//int main()
//{
//	int n = 0;
//	scanf("%d",&n);
//	Print(n);
//
//	return 0;
//}


//计算第n个斐波那契函数的值
// 
// 递归运算
//int Fib(int n)
//{
//	if (n <= 2)
//	{
//		return 1;
//	}
//	else
//	{
//		return Fib(n - 1) + Fib(n - 2);
//	}
//
//
//
//}
//
//int main()
//{
//	int n = 0;
//	scanf("%d",&n);
//
//	int sum = Fib(n);
//
//	printf("%d",sum);
//
//	return 0;
//}

//循环运算

//int fib(int n)
//{
//	int a = 1;
//	int b = 1;
//	int c = 1;
//	while (n > 2)
//	{
//		c = a + b;
//		a = b;
//		b = c;
//		n--;
//
//	}
//
//	return c;
//}
//
//
//
//
//int main()
//{
//	int n = 0;
//	
//	scanf("%d",&n);
//	
//	int sum = fib(n);
//
//	printf("%d",sum);
//
//	return 0;
//}


//汉诺塔问题
//当只有一个盘子的时候，直接把这个盘子丛A放到C处
//2个盘子时，把②盘子放到B处，把①盘子放到C处，再把②盘子放到C处
//3个盘子时候，③->C,②->B,③->B,这时B盘子有②③。①->C,③->A,②->C,③->C,这样就可以实现C盘中按大到小排列
//总结：把n-1个盘子借助C放到B处，放第n个盘子放到C处，再把这n-1个盘子借助空柱A移到C出实现递归
//
//void move(char pose1, char pose2)
//{
//	printf("%c -> %c \n", pose1, pose2);
//}
//
//
//void Hanoi(int n, char pose1, char pose2, char pose3)
//{
//	if (n == 1)
//	{
//		move(pose1, pose3);
//	}
//	else
//	{
//		Hanoi(n - 1, pose1, pose3, pose2);
//		move(pose1, pose3);
//		Hanoi(n - 1, pose2, pose1, pose3);
//	}
//
//
//}
//
//
//
//int main()
//{
//	Hanoi(1, 'A', 'B', 'C');
//	printf("\n");
//	Hanoi(2, 'A', 'B', 'C');
//	printf("\n");
//	Hanoi(3, 'A', 'B', 'C');
//	printf("\n");
//	return 0;
//}


//青蛙跳台阶问题
//n1 = 1,n2 = 2,n3 = 3,n4 = 5 前两个数相加等于第三个数








//以下为作业题目的解答



//1.作业内容
//递归和非递归分别实现求第n个斐波那契数
//
//例如：
//
//输入：5  输出：5
//
//输入：10， 输出：55
//
//输入：2， 输出：1


//int Fib1(int n)//递归解法
//{
//	if (n <= 2)
//	{
//		return 1;
//	}
//	else
//	{
//		return Fib1(n - 1) + Fib1(n - 2);
//	}
//}
//
//int Fib2(int n)//非递归(循环)解法
//{
//	int a = 1;
//	int b = 1;
//	int c = 1;
//	while (n>2)
//	{
//		c = a + b;
//		a = b;
//		b = c;
//		n--;
//	}
//	return c;
//}
//
//
//
//
//
//int main()
//{
//	printf("%d\n", Fib1(1));
//	printf("%d\n", Fib1(2));
//	printf("%d\n", Fib1(10));
//
//	printf("%d\n", Fib2(1));
//	printf("%d\n", Fib2(2));
//	printf("%d\n", Fib2(10));
//	return 0;
//}






//2.作业内容
//编写一个函数实现n的k次方，使用递归实现。

//int POW(int n, int k)
//{
//	if (k == 0)
//	{
//		return 1;
//	}
//	else if (k > 0)
//	{
//		return n * POW(n, --k);
//	}
//	else
//		return 1.0 / POW(n, -k);
//
//
//}
//
//
//int main()
//{
//	int n = 0;
//	int k = 0;
//	scanf("%d%d", &n, &k);
//	double ret = POW(n, k);
//	printf("%lf", ret);
//
//	return 0;
//}



//3.
//作业内容
//写一个递归函数DigitSum(n)，输入一个非负整数，返回组成它的数字之和
//
//例如，调用DigitSum(1729)，则应该返回1 + 7 + 2 + 9，它的和是19
//
//输入：1729，输出：19
//

//
//int Dig_Sum(int n)
//{
//	if (n > 9)
//	{
//		return Dig_Sum(n / 10) + n % 10;
//	}
//	else
//		return n;
//
//
//}
//
//int main()
//{
//	int n;
//	scanf("%d", &n);
//	int ret = Dig_Sum(n);
//	printf("%d", ret);
//
//	return 0;
//}